package leetcode.editor.cn.q301_600.q300;
//给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 
//
// 返回所有可能的结果。答案可以按 任意顺序 返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()())()"
//输出：["(())()","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：s = "(a)())()"
//输出：["(a())()","(a)()()"]
// 
//
// 示例 3： 
//
// 
//输入：s = ")("
//输出：[""]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 25 
// s 由小写英文字母以及括号 '(' 和 ')' 组成 
// s 中至多含 20 个括号 
// 
//
// 👍 855 👎 0

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 思路：先拿到 s 无效的括号 red，然后递归从 s 中拿字符来匹配 red，匹配到之后剩下的字符串如果合法就放到 list 中
 * <p>
 * 执行耗时:294 ms,击败了8.73% 的Java用户
 * 内存消耗:43.3 MB,击败了20.56% 的Java用户
 * <p>
 * 低分飘过，懒得看答案了
 */
public class Q301_RemoveInvalidParentheses {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        String s;

        // 多余的括号
        String red;

        ArrayList<String> al;

        public List<String> removeInvalidParentheses(String s) {
            this.s = s;
            Deque<Character> stack = new ArrayDeque<>();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.add('(');
                } else if (s.charAt(i) == ')') {
                    if (stack.isEmpty() || stack.peekLast() == ')') {
                        stack.add(')');
                    } else {
                        stack.pollLast();
                    }
                }
            }
            // 此时栈里就只剩下了多余的括号
            String str = "";
            while (!stack.isEmpty()) {
                str += stack.pollFirst();
            }
            red = str;

            al = new ArrayList<>();
            process(s, 0, "", 0);
            return al;
        }

        private void process(String curS, int si, String curRed, int redi) {
            if (curRed.equals(red) && !al.contains(curS) && checkStr(curS)) {
                al.add(curS);
                return;
            }

            while (redi < red.length() && si < curS.length()) {
                if (curS.charAt(si) != red.charAt(redi)) {
                    si++;
                    continue;
                }
                // 使用当前的 char
                process(curS.substring(0, si) + (si + 1 < curS.length() ? curS.substring(si + 1) : ""), si, curRed + curS.charAt(si), redi + 1);
                // 不使用当前的 char
                process(curS, si + 1, curRed, redi);
                break;
            }
        }

        private boolean checkStr(String curS) {
            Deque<Character> stack = new ArrayDeque<>();
            for (int i = 0; i < curS.length(); i++) {
                char c = curS.charAt(i);
                if (c == '(') {
                    stack.add('(');
                } else if (c == ')') {
                    if (stack.isEmpty() || stack.peekLast() != '(') {
                        return false;
                    }
                    stack.pollLast();
                }
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q301_RemoveInvalidParentheses().new Solution();
        // TO TEST
        System.out.println(solution.removeInvalidParentheses("()())()"));
        System.out.println(solution.removeInvalidParentheses("(a)())()"));
        System.out.println(solution.removeInvalidParentheses(")("));
    }
}